package app.util.algo;

import app.env.Data;
import app.env.Position;
import app.util.AppUtils;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Name: AStar
 * @Description:
 * @Author: colfish
 * @Date: 2021/5/18 16:59
 * 好好学习，天天向上！
 */
public class AStar {
    private static Logger logger = LogManager.getLogger(AppUtils.class);

    /**
     * 找到两个坐标之间移动的最小路径轨迹
     * @return 返回一个栈，存放从终点到起点的路径点
     */
    public static Stack<Position> findPath(int[][] board, int x1, int y1, int x2, int y2) {

        int[][] DIREC =  {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
                {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
        List<Position> openList = new ArrayList<>();
        List<Position> closeList = new ArrayList<>();
        boolean findFlag = false;
        Position termPos = null;
        // 起始点
        Position startPos = new Position(x1, y1, calcH(x1, y1, x2, y2));
        openList.add(startPos);
        do {
            // 通过在开启列表中找到F值最小的点作为当前点
            Position currentPos = openList.get(0);

            for (Position position : openList) {
                if (currentPos.F > position.F) {
                    currentPos = position;
                }
            }
            // 将找到的当前点放到关闭列表中，并从开启列表中删除
            closeList.add(currentPos);
            openList.remove(currentPos);

            //遍历当前点对应的4个相邻点
            for (int[] direc : DIREC) {
                int tmpX = currentPos.x + direc[0];
                int tmpY = currentPos.y + direc[1];
                if (tmpX < 0 || tmpX >= board.length || tmpY < 0 || tmpY >= board[0].length) {
                    continue;
                }
                //创建对应的点
                Position tmpPos = new Position(tmpX, tmpY, calcH(tmpX, tmpY, x2, y2), currentPos);
                //board中对应的值时障碍物或目标， 或对应的点已经在关闭列表中
                if (board[tmpX][tmpY] == Data.OBSTACLE_SIGNAL ||
                        board[tmpX][tmpY] == Data.TARGET_SIGNAL ||
                        closeList.contains(tmpPos)) {
                    continue;
                }
                //如果不在开启列表中，则加入到开启列表
                if (!openList.contains(tmpPos)) {
                    openList.add(tmpPos);
                } else {
                    // 如果已经存在开启列表中，则用G值考察新的路径是否更好，如果该路径更好，则把父节点改成当前格并从新计算FGH
                    Position prePos = null;
                    for (Position pos : openList) {
                        if (pos.x == tmpX && pos.y == tmpY) {
                            prePos = pos;
                            break;
                        }
                    }
                    if (tmpPos.G < prePos.G) {
                        prePos.setFatherPos(currentPos);
                    }
                }
            }
            // 判断终点是否在开启列表中
            for (Position tpos : openList) {
                if (tpos.x == x2 && tpos.y == y2) {
                    termPos = tpos;
                    findFlag = true;
                    break;
                }
            }

        } while(openList.size() != 0);

        if(!findFlag) {
            logger.info("no valid path!");
            return null;
        }

        Stack<Position> resStack = new Stack<Position>();

        if (termPos != null) {
            resStack.push(termPos);
            while(termPos.father != null) {
                termPos = termPos.father;
                resStack.push(termPos);
            }
        }
        return resStack;
    }

    /**
     * 计算某个格子的H值
     * @param tx 终点的x值
     * @param ty 终点的y值
     */
    private static int calcH(int x, int y, int tx, int ty) {
        int diff = Math.abs(x - tx) + Math.abs(y - ty);
        return diff * 10;
    }
}
